package com.kavin.collection.datastructure;

/**
 * 平衡二叉树
 *
 * @author 韩帅比
 * @create 2021-09-09 17:35
 */


/*创建AVLTree*/
class AVLTree {
    private AVLNode root;

    public AVLNode getRoot() {
        return root;
    }

    /*1.添加结点*/
    public void add(AVLNode node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    /*2.中序遍历*/
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("空树");
        }
    }


}

/*结点类*/
class AVLNode {
    int value;
    AVLNode left;
    AVLNode right;
    public AVLNode(int value) {
        this.value = value;
    }
    /*1.添加结点*/
    public void add(AVLNode node) {  //递归添加
        if (node == null) {
            return;
        }
        //判断传入结点的值和当前结点的值的大小
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else { //(node.value > this.value)
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
        if (bF() < -1) {    //右子树高
            if (right.bF() > 0) {
                right.rightRotate();
            }
            leftRotate();
        } else if (bF() > 1) {   //左子树高
            if (left.bF() < 0) {
                //先对根结点的左子树进行左旋转
                left.leftRotate();
            }
            //再对当前根结点进行右旋转
            rightRotate();
        }
    }
    /*9.左旋转,逆时针旋转*/
    private void leftRotate() {
        //1.创建新的结点，以当前根结点的值 作为 新结点的值
        AVLNode newNode = new AVLNode(value);
        //2.把新的结点的左子树 设为 当前根结点的左子树
        newNode.left = left;
        //3.把新的结点的右子树 设置成 当前根结点的右子树的左子树
        newNode.right = right.left;
        //4.把当前根结点的值 替换为 右子结点的值
        value = right.value;
        //5.把当前根结点的右子树 设置成 右结点的右子树
        right = right.right;
        //6.把当前根结点的左子树 设置为 新的结点
        left = newNode;
    }
    /*10.右旋转*/
    private void rightRotate() {
        //1.创建新的结点，以当前根结点的值 作为 新结点的值
        AVLNode newNode = new AVLNode(value);
        //2.把新的结点的右子树 设为 当前根结点的右子树
        newNode.right = right;
        //3.把新的结点的左子树 设置成 当前根结点的左子树的右子树
        newNode.left = left.right;
        //4.把当前根结点的值 替换为 左子结点的值
        value = left.value;
        //5.把当前根结点的左子树 设置成 左结点的左子树
        left = left.left;
        //6.把当前根结点的右子树 设置为 新的结点
        right = newNode;
    }
    /*2.中序遍历*/
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
    /*5.返回当前结点为根结点 的树的高度*/
    public int height() {
        System.out.println("========================1");
        int a = left == null ? 0 : left.height();
        System.out.println("========================2");
        int b = right == null ? 0 : right.height();
        System.out.println("========================3");
        return Math.max(a, b) + 1;
    }
    /*6.返回左子树的高度*/
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }
    /*7.返回右子树的高度*/
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }
    /*8.平衡因子*/
    public int bF() {
        return leftHeight() - rightHeight();
    }
    @Override
    public String toString() {
        return "AVLNode{" + "value=" + value + '}';
    }


    public static class AVLTreeDemo {
        public static void main(String[] args) {
            int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
            //创建一个 AVLTree对象
            AVLTree avlTree = new AVLTree();
            //添加结点
            for (int i = 0; i < arr.length; i++) {
                avlTree.add(new AVLNode(arr[i]));
            }
/*        //中序遍历
        avlTree.infixOrder();*/

            AVLNode node = avlTree.getRoot();
            int a = node.leftHeight();


/*        System.out.println("在平衡处理~~");
        System.out.println("树的高度=" + avlTree.getRoot().height());
        System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight());
        System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight());*/

        }
    }
}

